Đầu sự nghiệp

Koller bắt đầu tập luyện chơi bóng ở vị trí thủ môn,[2] nhưng lại chuyển sang vị trí tiền đạo kể từ khi anh bắt đầu sự nghiệp chuyên nghiệp với câu lạc bộ Sparta Prague của Séc. Anh có trận ra mắt Sparta vào mùa xuân năm 1995 trong trận gặp Benešov, anh vào sân thay người khi trận đấu còn 20 phút.[3] Năm 1996, Koller lọt vào mắt xanh của một đội bóng Bỉ và ký hợp đồng với câu lạc bộ Lokeren với mức phí ước tính là 102.000 euro.[2]

Anderlecht

Sau 3 năm thi đấu thành công, anh đã kết thúc ở vị thế là chân sút ghi nhiều bàn nhất tại giải bóng đá vô địch quốc gia Bỉ trong mùa giải cuối tại Lokeren, Koller được câu lạc bộ Anderlecht của Bỉ mời ký hợp đồng. Anh nhanh chóng xây dựng lối chơi bóng phối hợp ăn ý với tiền đạo người Canada Tomasz Radzinski, anh chơi xuất sắc trong mùa giải đầu tay và kiếm về cho anh dạng hiệu Chiếc giày vàng bóng đá Bỉ vào năm 2000. Cuối mùa giải, anh được câu lạc bộ Borussia Dortmund của Đức mua lại sau khi từ chối lời đề nghị hỏi mua từ một đội bóng Anh tên là Fulham.[4]